1. Field of the Invention
The present invention generally relates to operations planning in a process industry and, more particularly, to a method of designing a set of slabs from target orders in a near-optimal manner while satisfying design restrictions.
2. Background Description
General background information may be had by reference to the following two books:
1. Ahuja, R. K., Magnanti, T. L. and Orlin, J. B. (1993), Network Flows, Prentice Hall, N.J. PA0 2. Horowitz, E. and Sahni, S. (1978), Fundamentals of Data Structures, Computer Science Press, Inc. PA0 1. Orders need to compatible in terms of physical dimensions in order to be grouped together. Orders that have similar width and thickness requirements can be packed together. As we had mentioned before for inventory matching according to Ser. No. 09/047,275, it is possible to alter the thickness and width (within a range) by rolling. Therefore, orders with thickness and width close to each other can be grouped on the same slab. PA0 2. The second set of grouping constraints arise from process considerations in the hot/cold mill and the finishing line. These constraints can be represented using color constraints. More explicitly, we can associate with each order a color which represents the finishing operations that are required. As before, we can specify color constraints which limit the number of colors that can be grouped on each designed slab. PA0 1. In the first variation, we continue to assume a single group with a single allowable slab; however, we invoke the color constraints. This leads to a bin packing problem with colors constraints. PA0 2. In the second variation, we relax our earlier assumption of having a single group. In place of that assumption we allow multiple groups with multiple corresponding allowable slab weights. We can represent this problem with a bipartite graph with a node for each order and a corresponding slab node for each group that multiple orders can be packed into. We use arcs from orders to slabs to indicate the assignment restrictions. This is a variable bin packing problem with color constraints. Note that if the bipartite graph is complete, then the problem degenerates to a single bin packing problem with the bin representing the slab of the largest allowable weight. However, with sparse assignment restrictions, the variable bin packing problem with color constraints constitutes an interesting variation of the original problem. PA0 1. Because of its incremental approach to searching the space of matches, the speed of this algorithm depends critically on how close the actual optimal solution is to the relaxed solution generated by the linear program. For the slab design problem, both the integrality constraints of the DPU.sub.number and the color constraints render the relaxed problem to be a rather loose approximation to the actual problem. Hence, the branch-and-bound algorithm is very slow (a couple of hours) for even moderate sized problems. Such a response time is not acceptable in real world situations where the entire production plan (of which the slab design is a small part) has to be done within a couple of hours. PA0 2. Finally the branch-and-bound algorithm can optimize for only one objective at a time. The slab design problem has two major competing objectives: maximize designed slab size and minimize partial surplus. In order to solve for both these objectives, the algorithm has to be applied once for each objective by constraining the other objective at some desirable goal. This procedure is repeated until no further improvement in both objectives can be achieved. Since the algorithm response for each objective is slow, such a goal programming approach is too slow for real world applications.
Operations planning in a process industry typically begins with a order book which contains a list of orders that need to be satisfied. The initial two steps in an operations planning exercise involves (1) first trying to satisfy orders from the order book using leftover stock from the inventory and (2) subsequently designing productions units for manufacture from the remaining orders. Two important characteristics of a process industry are that the products are all manufactured based on the orders instead of being based on a forecast of the expected demand (as in retail or semiconductor manufacturing) and, as a consequence, the inventory is merely the stock of previously produced units which for reasons of quality could not be shipped to the customer.
The subject invention is a novel and fast computer-implemented method for the second of these problems from an optimization perspective. The second problem, i.e., designing production units, involves using the order book to design the size and number of production units that need to be manufactured. The goal of this design is to minimize the number of units that need to be manufactured, which for a given order book is equivalent to maximizing the average size of the production unit. This problem has a strong flavor of a grouping exercise where different orders are grouped together to form a slab (the manufacturing unit in a steel industry)--we call this the slab design problem. There are, once again, several constraints regarding which orders can be grouped together, based on grade and surface quality and weight considerations, which give rise to integrality constraints. The maximum allowable size of a slab for a potential group of orders is constrained based on manufacturing considerations. Additionally, each designed slab needs to be of a minimum size, and any group of orders weighing less than this minimum introduces a designed slab with some partial surplus. The partial surplus is clearly undesirable and needs to be minimized. This problem can be formulated as a variation of the variable size bin packaging problem.